package arrAndstr;

/*
    61. 旋转链表
 */
public class T61 {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode node = head;

        node.next = new ListNode(1);
        node = node.next;
        node.next = new ListNode(2);

        rotateRight(head, 4);
    }

    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;

        ListNode node = head;
        int len = 0;
        while (true) {
            if (node == null) break;
            len++;
            node = node.next;
        }

        // 成环
        node = head;
        while (true) {
            if (node.next == null) {
                node.next = head;
                break;
            }
            node = node.next;
        }

        // 找到旋转后的第一个元素  k=k%len 第 len-k+1 个 --> 走 len-k 步
        k = k%len;
        ListNode preNode = new ListNode();
        node = head;
        int step = 0;
        while (step < len - k) {
            step++;

            preNode = node;
            node = node.next;
        }

        // 切断环
        preNode.next = null;
        return node;
    }
}
